package code601_700.code30_40;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * 这里有 n 门不同的在线课程，按从 1 到 n 编号。给你一个数组 courses ，
 * 其中 courses[i] = [durationi, lastDayi] 表示第 i 门课将会 持续 上 durationi 天课，
 * 并且必须在不晚于 lastDayi 的时候完成。
 *
 * 你的学期从第 1 天开始。且不能同时修读两门及两门以上的课程。
 *
 * 返回你最多可以修读的课程数目。
 *
 * 输入：courses = [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
 * 输出：3
 * 解释：
 * 这里一共有 4 门课程，但是你最多可以修 3 门：
 * 首先，修第 1 门课，耗费 100 天，在第 100 天完成，在第 101 天开始下门课。
 * 第二，修第 3 门课，耗费 1000 天，在第 1100 天完成，在第 1101 天开始下门课程。
 * 第三，修第 2 门课，耗时 200 天，在第 1300 天完成。
 * 第 4 门课现在不能修，因为将会在第 3300 天完成它，这已经超出了关闭日期。
 *
 * 输入：courses = [[1,2]]
 * 输出：1
 *
 * 输入：courses = [[3,2],[4,3]]
 * 输出：0
 */
public class _630scheduleCourse {

    /**
     * 题解中的算法，有点妙，试着重现一下。方法栈是：优先队列+贪心
     *
     * 算法：我们需要一个数据结构支持“去除t值最大的那门课程”，因此我们可以使用优先队列大根堆。
     * 我们需要依次遍历每一门课程，当遍历到t，d时
     * 如果当前优先队列中的所有课程总时间与t之和小于等于d，则把t加入到优先队列中。
     * 如果当前优先队列中总时间与t之和大于d，则找出优先队列中的最大元素t，如果最大元素t大于当前t，则把最大元素t移除队列，把新的t加入进而优化空间。
     * @param courses
     * @return
     */
    public int scheduleCourse(int[][] courses) {
        // 以结束时间排序
        Arrays.sort(courses,(a,b)->a[1]-b[1]);
        // 因为默认为小根堆，所以需要加入lambda表达式
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((a,b)->b-a);
        int total = 0;
        for (int[] temp : courses) {
            int ti = temp[0];
            int di = temp[1];
            if(ti+total <= di){
                total += ti;
                priorityQueue.offer(ti);
            }else if(!priorityQueue.isEmpty()&&priorityQueue.peek()>ti){
                total -= priorityQueue.poll();
                total += ti;
                priorityQueue.offer(ti);
            }
        }
        return priorityQueue.size();
    }



}
